#include <stdio.h>
#include "single_linked_list.cpp"
#include <map>

using namespace std;

/***
 * 1. 带头结点的单链表 删除重复数据 并将其余数据进行递增排序
 * 2. 大根堆有序 查找大根堆oldvalue值 修改为newvalue
 * */

// 第一题 链表去重排序
void Sort(LinkedList &L)
{
    // 排序方式很多 这里使用插入排序
    LNode *p = L->next->next; // 旧链表指针
    LNode *q;                 // 新链表工作指针
    L->next->next = NULL;     // 断链 成为有序新链表

    while (p)
    {
        // 在新链表中找到当前p结点合适的位置
        q = L;
        while (q->next)
        {
            if (q->next->data < p->data)
            {
                // 插入
                LNode *r = p->next;
                p->next = q->next;
                q->next = p;
                p = r;
                break;
            }
            else
            {
                q = q->next;
            }
        }
        if (!q->next)
        {
            // p 为最大 插入最后
            q->next = p;
            p = p->next;
            q->next->next = NULL;
        }
    }
}

void DedupAndSort(LinkedList &L)
{
    map<int, bool> mp;
    LNode *ptr = L;
    while (ptr->next != NULL)
    {
        if (mp.find(ptr->next->data) != mp.end())
        {
            // 重复-删除元素
            LNode *cur = ptr->next;
            ptr->next = ptr->next->next;
            free(cur);
        }
        else
        {
            mp[ptr->next->data] = true;
            ptr = ptr->next;
        }
    }

    // 排序
    Sort(L);
}



int main()
{
    LinkedList L;
    InitList(L);

    // 插入
    ListAppend(L, 10);
    ListAppend(L, 5);
    ListAppend(L, 5);
    ListAppend(L, 5);
    ListAppend(L, 3);
    ListAppend(L, 10);
    PrintList(L);

    // 去重
    DedupAndSort(L);
    PrintList(L);

    return 0;
}